1. Field of the Invention
The present invention relates to an efficient implementation of DSP functions in a field programmable gate array (FPGA).
2. Description of the Related Art
Digital signal processing (DSP) has traditionally been done using enhanced microprocessors. Although DSP processors are programmable through software, yet the DSP processor hardware architecture used is not flexible. Therefore, the performance of the DSP processors is limited by fixed hardware architecture such as bus performance bottlenecks, a fixed number of multiply accumulate (MAC) blocks, fixed memory, fixed hardware accelerator blocks, and fixed data widths. Further the DSP processor's fixed hardware architecture is not suitable for certain applications that might require customized DSP function implementations.
FPGAs, on the other hand, can provide a fast, cost effective solution to many of today's complex demands for implementing DSP functionality, as FPGA is a general-purpose device that can be programmed by an end user to perform one or more selected functions. An FPGA typically includes an array of individually Configurable Logic Blocks (CLBs), each of which is programmably interconnected to the other CLB and to the input/output (I/O) pins via a programmable routing structure to provide the selected function.
Since the hardware of the FPGAs can be reconfigured, they offer complete hardware customization while implementing various DSP applications. Therefore, DSP systems implemented in FPGAs can have customized architecture, customized bus structure, customized memory, customized hardware accelerator blocks, and a variable number of MAC blocks.
The fundamental difference between a DSP processor and a generic processor lies in the DSP processor's hardware multiply-accumulate (MAC) block and specialized memory and bus structures to facilitate frequent data access commonly found in DSP applications. The MAC operation is usually the performance bottleneck in most DSP applications.
Until recently, FPGAs did not have hard IPs like memories or multipliers embedded in them. In the past few years, however, we have seen FPGAs with embedded silicon features that are ideal for DSP applications such as embedded memory, DSP blocks, and embedded processors that are well-suited for implementing DSP functions such as FIR filters, FFTs, correlators, equalizers, encoders, decoders, and arithmetic functions. Among these FPGA vendors are Xilinx, who provide embedded memories and multipliers, and Altera, who provide a complete DSP block and embedded memories for DSP applications.
FIG. 1 shows the architecture of the DSP block designed by Altera. Said DSP block has been described in detail in U.S. patent application No. 20030141898 entitled “Programmable logic devices with function-specific blocks”. This DSP block incorporates not only embedded multipliers but also accumulators to perform MAC operations. The operations that are possible with this architecture are:                1.MAC=MAC+INPUT        2.MAC=MAC−INPUT        
Another U.S. Pat. No. 6,573,749 filed by Xilinx incorporates embedded multipliers in its FPGAs for DSP applications. An embedded multiplier in Virtex II allows the multiplication of two 18-bit numbers. The 36-bit output is then fed via local routing resources to the CLBs for further processing. FIG. 2 shows the architecture of the Virtex II multiplier block.
Most of the DSP designs handle expressions of the form:y(n)=c1.y(n−1)+c2.y(n−2)+c3.y(n−3+ . . .  (1)y(n)=a+x(n).c1  (2)
The DSP block by Altera can implement a MAC operation, which is equation 1, in one DSP Block. However, the second equation (2) can only be implemented as y(n)=1.a+x(n).c1. In other words two multiplication operations would be required for its implementation. Further it allows the implementation of only a 4-tap FIR filter (18-bit precision) in each of its multifunction tiles (DSP Blocks). Since these multifunction tiles are not cascadable, any filter with more than 4 taps uses general-purpose routing resources and other general-purpose tiles for its complete implementation. And, as mentioned above, this architecture requires two clock cycles to add an extra coefficient.
Xilinx, on the other hand, provides a multiplier that can only implement the multiplication operation in the multiplier block while accumulation is carried out in the CLBs.